package summary;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/17 11:57
 * https://leetcode-cn.com/problems/01-matrix/
 */
public class Title542 {

    public static int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                }else{
                    mat[i][j] = -1;
                }
            }
        }
        //上下左右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            //向四周辐射
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                //mat[i][j] = -1表示未被访问过
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && mat[newX][newY] == -1) {
                    mat[newX][newY] = mat[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        return mat;
    }

    public static void main(String[] args) {

    }
}
